package leetcode.code077.Combinations;

import java.util.ArrayList;
import java.util.List;

public class Solution07701 extends Combinations {

	@Override
	public List<List<Integer>> combine(int n, int k) {
		return this.f(n, k, 1, 1);
	}

	private List<List<Integer>> f(int n, int k, int no, int min) {
//		System.out.println("f(" + no + "," + min + ")");
		if (no > k)
			return null;
		List<List<Integer>> result = new ArrayList<>();
		for (int i = min; i <= n - k + no; i++) {
			int num = i;
			List<List<Integer>> sublist = f(n, k, no + 1, num + 1);
			if (sublist != null && sublist.size() != 0) {
				for (List<Integer> sub : sublist) {
					sub.add(num);
					result.add(sub);
				}
			} else {
				List<Integer> list = new ArrayList<>();
				list.add(i);
				result.add(list);
			}

		}
		return result;
	}

	public static void main(String[] args) {
		Solution07701 so = new Solution07701();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
